import static com.sun.deploy.net.MessageHeader.merge;

public class Sort {
    //直接插入排序
    public static void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int tmp=arr[i];
            int j=i-1;
            for (; j >=0 ; j--) {
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else{
                    //arr[j+1]=tmp;
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    //希尔排序
    public static void shellSort(int[] arr) {
        int gap= arr.length;
        while (gap>1){
            gap/=2;
            shell(arr,gap);
        }
    }

    public static void shell(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp=arr[i];
            int j=i-gap;
            for (; j >=0 ; j-=gap) {
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }


    //直接选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            swap(arr,minIndex,i);
        }
    }

    public static void selectSort2(int[] arr) {
        int left=0;
        int right= arr.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i<=right; i++) {
                if(arr[i]<arr[minIndex]){
                    minIndex=i;
                }
                if(arr[i]>arr[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(arr,left,minIndex);
            if(maxIndex==left){//如果最大值就是下标为left的值，最小值交换的时候就会把最大值交换走
                maxIndex=minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }


    //冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) { //5个数据就排4次
            boolean flg=false;
            for (int j = 0; j < arr.length-1-i; j++) {  //-i是每次比较比上一次少一次
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                return;
            }
        }
    }

    //快速排序
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);

    }

    public static void quick(int[] arr,int start,int end) {
        if(start>=end) return;  //左边是一个节点或者一个节点都没有
        int pivot=partitionHoare(arr,start,end);
       //int pivot=partitionHole(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);

    }

    public static int partitionHoare(int[] arr,int left,int right) {
        int key=arr[left];
        int i=left;
        while(left<right){
            //为什么从右边开始而不是从左边开始?
            //如果先走左边可能会出现相遇的是大的数据，最后把大的数据放到了最前面
            while(left<right&&arr[right]>=key){
                right--;
            }
            while(left<right&&arr[left]<=key){
                left++;
            }
            swap(arr,left,right);
        }
        //相遇的位置和i位置进行交换
        swap(arr,i,left);
        return left;
    }

    //挖坑法
    public static int partitionHole(int[] arr,int left,int right) {
        int tmp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=tmp){  //arr[right]>=tmp为什么要有=？  不等于可能陷入死循环
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;
        return left;
    }

    //堆排序
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array,int parent, int length) {
        int child=2*parent+1;
        while(child<length){
            if(child+1<length&&array[child]<array[child+1]){ //有右孩子并且左孩子比右孩子小
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

    public static void heapSort(int[] array){
        createHeap(array);  //创建大根堆
        int end= array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }


    //归并排序
    public static void mergeSort(int[] arr){
        mergeSortFun(arr,0, arr.length-1);
    }
    private static void mergeSortFun(int[] arr,int start,int end){
        if(start>=end){
            return;
        }
        //分解
        int mid=(start+end)/2;
        mergeSortFun(arr,start,mid);
        mergeSortFun(arr,mid+1,end);
        //合并
        merge(arr,start,mid,end);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        //定义一个新的数组
        int[] tmpArr=new int[right-left+1];
        int k=0;  // tmpArr数组的下标
        //同时满足下面的情况证明两个归并段都有数据
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                tmpArr[k++]=arr[s1++];
            }else{
                tmpArr[k++]=arr[s2++];
            }
        }
        //如果还有剩余的数据直接放回数组
        while(s1<=e1){
            tmpArr[k++]=arr[s1++];
        }
        while(s2<=e2){
            tmpArr[k++]=arr[s2++];
        }
        //需要把排好序的数据拷贝回原来的数组arr中
        for (int i = 0; i < tmpArr.length; i++) {
            arr[i+left]=tmpArr[i];//+left是拷贝的时候不要覆盖了0下标开始拷贝的那一部分数据
        }
    }


}
